//https://leetcode.cn/problems/pascals-triangle/?envType=study-plan-v2&envId=top-100-liked
package Dynamic_Program;
import java.util.ArrayList;
import java.util.List;

public class Pascals_triangle {

    public static List<List<Integer>> solution(int numRows){
        List<List<Integer>> total = new ArrayList<>(); //返回的数组
        // 当情况为 1 时
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        total.add(list1);
        if(numRows==1){
            return total;
        }
        // 当情况为 2 时
        List<Integer> list2 = new ArrayList<>();
        list2.add(1);
        list2.add(1);
        total.add(list2);
        if(numRows==2){
            return total;
        }

        for(int i=2;i<numRows;i++){
            List<Integer> a = new ArrayList<>();
            a.add(1);
            // 取出上一层的list
            List<Integer> last = total.get(i-1);
            for(int j=1;j<i;j++){
                a.add(last.get(j-1)+ last.get(j));
            }
            a.add(1);
            total.add(a);
        }

        return total;
    }
}
